package MiddlePractice;

import org.junit.Test;

public class Demo62 {
	
//	62. 不同路径
//	一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
//
//	机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
//
//	问总共有多少条不同的路径？
	
	//1.原始方法
	public int uniquePaths(int m, int n) {
		
		int[][] dp = new int[m][n];
		dp[0][0] = 1;
		for(int i=0; i<m; i++) {
			for(int j=0; j<n; j++) {
				if(i-1 >= 0) {
					//上面有路过来
					dp[i][j] += dp[i-1][j];
				}
				if(j-1 >= 0) {
					dp[i][j] += dp[i][j-1];
				}
			}
		}
		return dp[m-1][n-1];

    }
	
	//2.内存占用的优化
	public int my_uniquePaths(int m, int n) {
		
		int[] dp = new int[n];
		int ans = 1;
		int temp = 0;
		
		for(int i=0; i<m; i++) {
			for(int j=0; j<n; j++) {
				if(i-1 >= 0) {
					ans += dp[j];
				}
				if(j-1 >= 0) {
					ans += temp;
				}
				temp = ans;
				dp[j] = ans;
				ans = 0;
				
				
			}
		}
		return dp[n-1];

    }
	
	@Test
	public void test_62() {
		System.out.println(my_uniquePaths(1,1));
	}
}
